use std::ptr;

struct QueueEntry {
    data: i32,
    prev: *mut QueueEntry,
    next: *mut QueueEntry,
}

pub struct Queue {
    head: *mut QueueEntry,
    tail: *mut QueueEntry,
}

impl Queue {
    pub fn new() -> Self {
        Queue {
            head: ptr::null_mut(),
            tail: ptr::null_mut(),
        }
    }

    pub fn free(&mut self) {
        while !self.is_empty() {
            unsafe { self.pop_head(); }
        }
    }

    pub fn push_head(&mut self, data: i32) -> bool {
        let new_entry = Box::new(QueueEntry {
            data,
            prev: ptr::null_mut(),
            next: self.head,
        });

        let raw_new_entry = Box::into_raw(new_entry);

        if self.head.is_null() {
            // If the queue was previously empty, both the head and tail must be pointed at the new entry
            self.head = raw_new_entry;
            self.tail = raw_new_entry;
        } else {
            // First entry in the list must have prev pointed back to this new entry
            unsafe { (*self.head).prev = raw_new_entry; }
            // Only the head must be pointed at the new entry
            self.head = raw_new_entry;
        }

        true
    }

    pub fn pop_head(&mut self) -> Option<i32> {
        if self.is_empty() {
            return None;
        }

        // Unlink the first entry from the head of the queue
        let entry = unsafe { Box::from_raw(self.head) };
        self.head = entry.next;

        let result = entry.data;

        if self.head.is_null() {
            // If doing this has unlinked the last entry in the queue, set tail to NULL as well.
            self.tail = ptr::null_mut();
        } else {
            // The new first in the queue has no previous entry
            unsafe { (*self.head).prev = ptr::null_mut(); }
        }

        Some(result)
    }

    pub fn peek_head(&self) -> Option<i32> {
        if self.is_empty() {
            None
        } else {
            unsafe { Some((*self.head).data) }
        }
    }

    pub fn push_tail(&mut self, data: i32) -> bool {
        let new_entry = Box::new(QueueEntry {
            data,
            prev: self.tail,
            next: ptr::null_mut(),
        });

        let raw_new_entry = Box::into_raw(new_entry);

        if self.tail.is_null() {
            // If the queue was previously empty, both the head and tail must be pointed at the new entry
            self.head = raw_new_entry;
            self.tail = raw_new_entry;
        } else {
            // The current entry at the tail must have next pointed to this new entry
            unsafe { (*self.tail).next = raw_new_entry; }
            // Only the tail must be pointed at the new entry
            self.tail = raw_new_entry;
        }

        true
    }

    pub fn pop_tail(&mut self) -> Option<i32> {
        if self.is_empty() {
            return None;
        }

        // Unlink the first entry from the tail of the queue
        let entry = unsafe { Box::from_raw(self.tail) };
        self.tail = entry.prev;

        let result = entry.data;

        if self.tail.is_null() {
            // If doing this has unlinked the last entry in the queue, set head to NULL as well.
            self.head = ptr::null_mut();
        } else {
            // The new entry at the tail has no next entry.
            unsafe { (*self.tail).next = ptr::null_mut(); }
        }

        Some(result)
    }

    pub fn peek_tail(&self) -> Option<i32> {
        if self.is_empty() {
            None
        } else {
            unsafe { Some((*self.tail).data) }
        }
    }

    pub fn is_empty(&self) -> bool {
        self.head.is_null()
    }
}

impl Drop for Queue {
    fn drop(&mut self) {
        self.free();
    }
}
